package com.sheng.leetcode.year2025.month10.day12;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author by ls
 * @date 2025/10/13
 * <p>
 * 3539. 魔法序列的数组乘积之和<p>
 * <p>
 * 给你两个整数 M 和 K，和一个整数数组 nums。<p>
 * 一个整数序列 seq 如果满足以下条件，被称为 魔法 序列：<p>
 * seq 的序列长度为 M。<p>
 * 0 <= seq[i] < nums.length<p>
 * 2^seq[0] + 2^seq[1] + ... + 2^seq[M - 1] 的 二进制形式 有 K 个 置位。<p>
 * 这个序列的 数组乘积 定义为 prod(seq) = (nums[seq[0]] * nums[seq[1]] * ... * nums[seq[M - 1]])。<p>
 * 返回所有有效 魔法 序列的 数组乘积 的 总和 。<p>
 * 由于答案可能很大，返回结果对 10^9 + 7 取模。<p>
 * 置位 是指一个数字的二进制表示中值为 1 的位。<p>
 * <p>
 * 示例 1:<p>
 * 输入: M = 5, K = 5, nums = [1,10,100,10000,1000000]<p>
 * 输出: 991600007<p>
 * 解释:<p>
 * 所有 [0, 1, 2, 3, 4] 的排列都是魔法序列，每个序列的数组乘积是 1013。<p>
 * <p>
 * 示例 2:<p>
 * 输入: M = 2, K = 2, nums = [5,4,3,2,1]<p>
 * 输出: 170<p>
 * 解释:<p>
 * 魔法序列有 [0, 1]，[0, 2]，[0, 3]，[0, 4]，[1, 0]，[1, 2]，[1, 3]，[1, 4]，[2, 0]，[2, 1]，[2, 3]，[2, 4]，[3, 0]，[3, 1]，[3, 2]，[3, 4]，[4, 0]，[4, 1]，[4, 2] 和 [4, 3]。<p>
 * <p>
 * 示例 3:<p>
 * 输入: M = 1, K = 1, nums = [28]<p>
 * 输出: 28<p>
 * 解释:<p>
 * 唯一的魔法序列是 [0]。<p>
 * <p>
 * 提示:<p>
 * 1 <= K <= M <= 30<p>
 * 1 <= nums.length <= 50<p>
 * 1 <= nums[i] <= 10^8<p>
 */
public class LeetCode3539 {

    @Test
    public void test() {
        int m = 5, k = 5;
        int[] nums = {1, 10, 100, 10000, 1000000};
//        int m = 2, k = 2;
//        int[] nums = {5, 4, 3, 2, 1};
//        int m = 1, k = 1;
//        int[] nums = {28};
        System.out.println(new Solution().magicalSum(m, k, nums));
    }
}

class Solution {
    private static final int MOD = 1_000_000_007;
    private static final int MX = 31;

    // F[i] = i!
    private static final long[] F = new long[MX];
    // INV_F[i] = i!^-1
    private static final long[] INV_F = new long[MX];

    static {
        F[0] = 1;
        for (int i = 1; i < MX; i++) {
            F[i] = F[i - 1] * i % MOD;
        }

        INV_F[MX - 1] = pow(F[MX - 1], MOD - 2);
        for (int i = MX - 1; i > 0; i--) {
            INV_F[i - 1] = INV_F[i] * i % MOD;
        }
    }

    private static long pow(long x, int n) {
        long res = 1;
        for (; n > 0; n /= 2) {
            if (n % 2 > 0) {
                res = res * x % MOD;
            }
            x = x * x % MOD;
        }
        return res;
    }

    public int magicalSum(int m, int k, int[] nums) {
        int n = nums.length;
        int[][] powV = new int[n][m + 1];
        for (int i = 0; i < n; i++) {
            powV[i][0] = 1;
            for (int j = 1; j <= m; j++) {
                powV[i][j] = (int) ((long) powV[i][j - 1] * nums[i] % MOD);
            }
        }

        int[][][][] memo = new int[n][m + 1][m / 2 + 1][k + 1];
        for (int[][][] a : memo) {
            for (int[][] b : a) {
                for (int[] c : b) {
                    Arrays.fill(c, -1);
                }
            }
        }
        return (int) (dfs(0, m, 0, k, powV, memo) * F[m] % MOD);
    }

    private long dfs(int i, int leftM, int x, int leftK, int[][] powV, int[][][][] memo) {
        int c1 = Integer.bitCount(x);
        // 可行性剪枝
        if (c1 + leftM < leftK) {
            return 0;
        }
        // 无法继续选数字
        if (i == powV.length || leftM == 0 || leftK == 0) {
            return leftM == 0 && c1 == leftK ? 1 : 0;
        }
        if (memo[i][leftM][x][leftK] != -1) {
            return memo[i][leftM][x][leftK];
        }
        long res = 0;
        // 枚举 I 中有 j 个下标 i
        for (int j = 0; j <= leftM; j++) {
            // 这 j 个下标 i 对 S 的贡献是 j * pow(2, i)
            // 由于 x = S >> i，转化成对 x 的贡献是 j
            int bit = (x + j) & 1; // 取最低位，提前从 leftK 中减去，其余进位到 x 中
            long r = dfs(i + 1, leftM - j, (x + j) >> 1, leftK - bit, powV, memo);
            res = (res + r * powV[i][j] % MOD * INV_F[j]) % MOD;
        }
        return memo[i][leftM][x][leftK] = (int) res;
    }
}

